Conjunto Regular

Dado un Alfabeto Σ, definimos un conjunto regular sobre el mismo de la siguiente manera:

1. ∅, el conjunto vacío, es un conjunto reguar.
2. {ε}, el Lenguaje con solo la cadena vacía, es un conjunto regular.
3. Para cada a ∈ Σ, el conjunto {a}, es un conjunto regular.
4. Si P y Q son conjuntos regulares sobre Σ, entonces también lo son:
   • P ∪ Q
   • P⋅Q
   • P ^* y Q ^*, las clausuras sobre P y Q
5. Si P es un conjunto regular, entonces (P) es el mismo lenguaje regular.
6. Nada más es un conjunto regular.

Lenguaje Regular

Un Lenguaje L ⊆ Σ^* es regular si y solo si es un Conjunto Regular. Es decir, si L es:

• ∅
• {ε}
• {a} | a ∈ Σ

o puede obtenerse de loas anteriores mediante un número finito de operaciónes de unión, concatenación, y Clausura.

Expresión Regular

Una expresión regular sobre un Alfabeto Σ es una manera conveniente de denotar un Conjunto Regular sobre dicho Alfabeto.

Una expresión regular se define de la siguiente manera:

1. ∅ denota el Conjunto Regular ∅.
2. ε denota {ε}.
3. a, con a ∈ Σ, denota {a}
4. Si p y q son expresiones regulares, entonces:
   • p y q denotan los conjuntos regulares P y Q respectivamente.
   • (p|q) denota P ∪ Q.
   • (p⋅q) denota P⋅Q.
   • (p)^* denota P ^*
5. Nada más es una expresión regular.

Por conveniencia definimos:

(p)⁺ = (p)⋅(p)*

Precedencia en Expresiones Regulares

Podemos eliminar los paréntesis en una expresión regular cuando ello no produzca ambiguedad si definimos que la precedencia de los operadores es la siguiente:

1. ^*, la Clausura
2. ⋅, la concatenacion
3. |, la union

En aplicaciones prácticas, puede usarse el símbolo + en lugar de | en las expresiones regulares.

Ejemplos

01 ⇒ {01}
0 ^* ⇒ {ε, 0, 00, 000, 000, ... }
(0|1)^* ⇒ {e, 0, 1, 00, 01, 10, 11, 000, ... }
(a|b)(a|b|c)* ⇒ {a, b, aa, ab, ac, ba, bb, bc, aaa, ...}

Propiedades Algebraicas de las Expresiones Regulares

Si p, q, y r son expresiones regulares, entonces:

1. p|q = q | p
2. ∅^* = ε
3. p | (q|r) = (p|q) | r
4. p⋅(q|r) = p⋅q | p⋅r
5. p⋅(q⋅r) = (p⋅q)⋅r
6. (p|q).r = p.r | q.r
7. p⋅ε = e⋅p = p
8. Ø⋅p = p⋅Ø = Ø
9. p ^* = p | p ^*
10. (p ^*) ^* = p ^*
11. p|p = p
12. p|Ø = Ø|p = p;

Concordancia

Una Cadena concuerda con una Expresion Regular si dicha Cadena pertenece al Conjunto Regular denotado por la expresión.

La Cadena:

abbba

concuerda con la expresión regular:

ab*a

Una Expresion Regular concuerda con el conjunto de cadenas en el Conjunto Regular que denota.

La expresión regular:

a(b|c)a

concuerda con el conjunto:

{aba, aca}

Expresiones Regulares en la Vida Real

Las Expresiones Regulares se usan en diversas áreas distintas a la de los compiladores. Por ejemplo, los editores de texto y los Ambientes Integrados de Desarrollo de software suelen incluir facilidades con Expresiones Regulares para la búsqueda y sustitución de texto.

Existen también librerías de manejo de Expresiones Regulares para la mayoría de los lenguajes de programación, y hay lenguajes como Perl y AWK, cuyo diseño gira en torno a las Expresiones Regulares.

Extensiones

Las implementaciones de Expresiones Regulares normalmente proveen cambios en la notación y extensiones que hacen más fácil escribir una Expresion Regular.

A continuación se describen algunas de las modificaciones y extensiones más frecuentes. El alfabeto subyacente en todos los casos es:

Σ = { el juego de caracteres LATIN-1 (ISO 8859-1) }

. El punto (any)

El símbolo . concuerda con cualquier símbolo del alfabeto subyacente. Por ejemplo, la expresión regular:

ca.a

concuerda con las cadenas (produce el Conjunto Regular):

{cama, casa, cara, cada, ca5a, ... }

Para lograr la Concordancia con un punto, hay que preceder el punto de una barra invertida (backslash).

ca\.a

concuerda únicamente con la cadena:

{ca.a}

El símbolo de barra invertida se usa en las Expresiones Regulares como símbolo de escape, es decir para cambiar el significado del siguiente símbolo de especial a normal, o viceversa.

La siguiente Expresion Regular:

3.1416

concuerda con muchas más cadenas que "3.1416". Para hacer que la expresión solo concuerde con esa aproximación del número PI, hay que escribirla así:

3\.1416

Formalmente, el símbolo "." corresponde a la Expresion Regular:

∪ {a} ∀ a ∈ Σ

* y + para Clausura y Clausura positiva

(p)* = (p)^*
(p)+ = (p)⁺

Para lograr la concordancia con * o + es necesario usar el símbolo de escape.

? Para cero o una vez

El símbolo ? hace que la Expresion Regular anterior concuerde cero veces o una vez. Por ejemplo, la Expresion Regular:

m?etano

concuerda con:

{metano, etano}

Al igual que con el punto, para lograr Concordancia con un signo de interrogación, hay que usar el símbolo de escape y escribir:

\?

Formalmente:

(p)? = (p|ε)

{n,m} Para de n a m veces

Una expresión de la forma

(p){n,m}, m > n

concuerda p con las cadenas que contengan entre n y m concatenaciones de p. Por ejemplo, la Expresion Regular:

ab{3,5}c

concuerda con:

{abbbc, abbbbc, abbbbbc }

Formalmente:

p{n,m} = p ⁿ | p ⁿ⁺¹ | ... | p ^m |

[ ] Para conjuntos de caracteres

Las expresiones en corchetes [ ] contienen listas de símbolos separadas por comas, y concuerdan con cualquiera de esos s?mbolos. Por ejemplo, la e.r.:

[a,b,c]

concuerda con:

{a, b, c}

únicamente. También pueden usarse rangos de símbolos separándolos con un quión:

[a-z]

una Expresion Regular así concuerda con cualquiera de los símbolos entre la 'a' y la 'z' según el orden lexicográfico del alfabeto subyacente. Como la mayoría de los órdenes lexicográficos tienen a las letras mayúsculas, las minúsculas, y los dígitos en el orden esperado, las expresiones con corchetes resultan muy útiles.

Por ejemplo, los identificadores válidos en el lenguaje de programación Pascal, concuerdan con esta Expresion Regular:

[_,A-Z,a-z][_,A-Z,a-z,0-9]*

Para incluir un guión entre los símbolos a concordar en una expresión en corchetes, se lo puede incluir de primero o último:

[123-]

concuerda con:

{1, 2, 3, -}

[^ ] Inversos de Conjuntos

Si el primer símbolo despu?s del corchete de apertura es uno de acento circunflejo (caret), entonces la expresión concuerda con lo contrario a lo que concordaría sin dicho símbolo:

[^a-z]

concuerda con cualquier símbolo que no sea una letra minúscula.

^ y $, comienzo y fin de la secuencia

El símbolo ^ concuerda con el inicio de la secuencia (o con el inicio de la línea de texto de entrada, dependiendo del software y su configuración), y el símbolo $ concuerda con el final de una secuancia (o con el final de la línea).

La Expresion Regular:

^$

concuerda con las secuencias vacías (el conjunto {ε}).

La expresión:

^ +

concuerda con las líneas que comienzan por uno o más blancos.

Secuencias de Escape

Muchos lenguajes de expresiones regulares, como el incluido en el lenguaje de programación Perl, definen una serie de muy útiles secuencias de escape:

• \t Concuerda con el caracter de tabulación.
• \n Concuerda con el fin de línea.
• \r Concuerda con el caracter de regreso de línea (retorno de carro).
• \w Concuerda con caracteres de palabras (alfanuméricos y _ ).
• \W Concuerda con el complemento de \w.
• \s Concuerda con los espacios en blanco (incluyendo el de tabulación, fin de línea, y regreso de línea los espacios).
• \S Concuerda con el complemento de \s.
• \d Concuerda con un dígito.
• \D Concuerda con lo que no sea un dígito.

() para agrupar y más

En muchas librerías de Expresiones Regulares, los paréntesis tienen un significado adicional al de las Expresiones Regulares formales. Los paréntesis hacen que el intérprete de Expresiones Regulares recuerde la secuencia que concordó con la sub-expresión y permita usarla en otras sub-expresiones, o en sustituciones.

Uno de los usos más frecuentes de los paréntesis es tratar de concordar la misma secuencia dos veces. Usualmente, se representa con \n a la cadena concordada por la sub-expresión entre paréntesis n. Por ejemplo, la expresión:

(\w+)\s*:=.*\W\1\W.*

trata de encontrar las asignaciones de pascal en las que el identificador asignado aparezca en en el lado derecho.

Otro uso frecuente de las sub-expresiones delimitadas por paréntesis es en la búsqueda y substitución. En esos casos, suele representarse por $n la cadena concordada por la sub-expresión entre paréntesis n. Por ejemplo, podríamos usar la siguiente Expresion Regular para intercambiar el orden de los elementos en una tabla:

 reemplazar(entrada, '(\\w*)\\s*,\\s*(\\w+);', '$2, $1;');

Definición Regular

Las Expresiones Regulares son una manera conveniente de describir los patrones asociados a los Componentes Lexicos, sobre todo cuando existen métodos muy eficientes de hacer análisis léxico usando expresiones regulares. Por ello la mayoría de los analizadores léxicos y las herramientas que los producen usan Expresiones Regulares para describir los Componentes Lexicos.

Dada una relación de orden total sobre los símbolos del alfabeto en cuestión, podemos usar la abreviación:

a _i..a _k con a _i...a _k ∈ Σ

para referirnos a la expresión regular:

a _i | a _i+1 | a _i+2 | ... | a _k

Entoces, podemos escribir definiciones de Componentes Lexicos así:

letra = a..z
digito = 0..9
identificador = letra . (letra | digito)*

Una definición como la anterior se llama una definición regular.

Definir el conjunto de Componentes Lexicos de un lenguaje de programación usando una definición regular es algo muy usual.